package class21;

/**
 * @author YZY
 * @since 2022/8/23 17:44
 * 给定5个参数，N，M，row，col，k
 * 表示在N*M的区域上，醉汉Bob初始在(row,col)位置
 * Bob一共要迈出k步，且每步都会等概率向上下左右四个方向走一个单位
 * 任何时候Bob只要离开N*M的区域，就直接死亡
 * 返回k步之后，Bob还在N*M的区域的概率
 */
public class Code05_BobDie {

    /**
     * 暴力尝试
     */
    public static double bobDie1(int n, int m, int row, int col, int k) {
        return (double) process1(n, m, row, col, k) / Math.pow(4, k);
    }

    private static int process1(int n, int m, int row, int col, int rest) {
        if (row < 0 || row == n || col < 0 || col == m) {
            return 0;
        }
        if (rest == 0) {
            return 1;
        }
        int up = process1(n, m, row - 1, col, rest - 1);
        int right = process1(n, m, row, col + 1, rest - 1);
        int down = process1(n, m, row + 1, col, rest - 1);
        int left = process1(n, m, row, col - 1, rest - 1);
        return up + right + down + left;
    }

    /**
     * 记忆化搜索
     */
    public static double bobDie2(int n, int m, int row, int col, int k) {
        int[][][] dp = new int[n][m][k + 1];
        return (double) process2(n, m, row, col, k, dp) / Math.pow(4, k);
    }

    private static int process2(int n, int m, int row, int col, int rest, int[][][] dp) {
        if (row < 0 || row == n || col < 0 || col == m) {
            return 0;
        }
        if (dp[row][col][rest] != 0) {
            return dp[row][col][rest];
        }
        if (rest == 0) {
            return 1;
        }
        int up = process2(n, m, row - 1, col, rest - 1, dp);
        int right = process2(n, m, row, col + 1, rest - 1, dp);
        int down = process2(n, m, row + 1, col, rest - 1, dp);
        int left = process2(n, m, row, col - 1, rest - 1, dp);
        return dp[row][col][rest] = up + right + down + left;
    }

    /**
     * 动态规划
     */
    public static double bobDie3(int n, int m, int r, int c, int k) {
        int[][][] dp = new int[n][m][k + 1];
        for (int row = 0; row < n; ++row) {
            for (int col = 0; col < m; ++col) {
                dp[row][col][0] = 1;
            }
        }
        for (int rest = 1; rest <= k; ++rest) {
            for (int row = 0; row < n; ++row) {
                for (int col = 0; col < m; ++col) {
                    int up = pick(n, m, row - 1, col, rest - 1, dp);
                    int right = pick(n, m, row, col + 1, rest - 1, dp);
                    int down = pick(n, m, row + 1, col, rest - 1, dp);
                    int left = pick(n, m, row, col - 1, rest - 1, dp);
                    dp[row][col][rest] = up + right + down + left;
                }
            }
        }
        return dp[r][c][k] / Math.pow(4, k);
    }

    private static int pick(int n, int m, int row, int col, int rest, int[][][] dp) {
        if (row < 0 || row == n || col < 0 || col == m) {
            return 0;
        }
        return dp[row][col][rest];
    }

    public static void main(String[] args) {
        // System.out.println(bobDie1(6, 6, 10, 50, 50));
        int n = 5, m = 5;
        int r = 2, c = 2;
        int k = 5;
        System.out.println(bobDie1(n, m, r, c, k));
        System.out.println(bobDie2(n, m, r, c, k));
        System.out.println(bobDie3(n, m, r, c, k));
    }

}
